The present invention relates generally to joining of fragments of an image to assemble the complete image, and particularly to accurately joining multiple image fragments.
Today, image processing devices allow images to be "captured" by computer systems by, e.g., scanning an image to obtain a digital representation of the image. Also, digital representations of images can be printed to generate a hard copy of the image. Examples of image processing devices are copiers, fax machines and scanners. These systems now use advanced technology to allow a human operator to manipulate the captured image by reducing, enlarging, adjusting the contrast, resolution or color of images, etc. While today's basic image processing devices are well-suited to handling standard size images, such as an image on an 8.5".times.11" sheet of paper, problems arise in these devices where an oversize image needs to be broken into image fragments in order to capture the image into a device and the fragments need to be reassembled for printing or other further processing.
For example, a problem with copy machines arises when it is desired to copy an oversize image, such as a map or poster. This is because the configuration of the copy machine will usually allow only portions, or fragments, of the oversize image to be scanned in each pass of the copier's scanning mechanism. This means that the human user of the copier needs to manually position the oversize image and make multiple scans of portions of the map or poster. Because the user must visually align the oversize image on the copier's platen, often without the aid of any registration marks, the user ends up with a hodgepodge collection of non-uniform fragments of the oversize image spread out over the papers. In the worst case, the user must then manually assemble the image fragments by cropping and taping together the pages.
Similarly, fax machines are limited to accepting paper of fixed and relatively small dimensions. If an oversize document is wider than that allowable by the fax machine, the document must be broken up into smaller images on smaller sheets of paper. The oversize image is then transmitted as several pieces to a receiving fax machine. A user at the receiving fax machine then goes through a similar process to piece together the oversize document's image from the multiple fragments of the document.
The process of automatically aligning image fragments to reproduce an original image is known as image registration. Some prior art image registration techniques were primarily developed for applications in the remote sensing field, e.g. constructing a composite satellite image of a large area from multiple photographs taken at different satellite positions.
These techniques, however, cannot be effectively applied to the office copier environment. On the one hand, long response times cannot be tolerated in copier applications. On the other hand, image registration techniques used in remote sensing must not only translate and rotate image fragments relative one another to align them, but must also correct for nonlinear effects, aspect, scale, changing contrast, and other effects.
Image registration techniques developed for the office environment all suffer from one or more shortcomings. One technique relies on marks that must be specially applied to the original large format document. In accordance with another technique, a large format document is sequentially scanned in segments. Pairs of image fragments are then registered to one another in sequence.
This technique cannot provide professional quality in situations where more than two overlapping fragments are to be aligned. Consider the situation in FIG. 1 where 4 overlapping image fragments 2, 4, 6, and 8 have been aligned with one another in accordance with the prior art technique. Essentially, the prior art technique uses pairwise alignment to align image fragment 2 with image fragment 4, image fragment 4 with image fragment 6, and image fragment 6 with image fragment 8. The alignments of image fragment pairs 2 and 4, 4 and 6, and 6 and 8 are acceptable. However, the alignment between image fragment 2 and image fragment 8 is unacceptable. This is because imperceptible errors in the pairwise alignment accumulate to the point that the alignment error between image fragments 2 and 8 is perceptible. Since many applications will require more than two image fragments to be joined, this type of alignment error propagation over multiple fragments represents a serious shortcoming of the prior art.